package oj_leetcode;

import java.util.HashMap;
import java.util.Map;

public class WordSearch {


    public boolean exist(char[][] board, String word) {
        char[] cWord = word.toCharArray();
        // dfs
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                boolean[][] record = new boolean[board.length][board[0].length];
                if (dfs(board, record, i, j, cWord, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean dfs(char[][] board, boolean[][] record, int i, int j, char[] cWord, int currIndex) {

        if (currIndex == cWord.length) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || record[i][j]) {
            return false;
        }
        record[i][j] = true;
        char curr = board[i][j];
        if (cWord[currIndex] == curr) {
            currIndex++;
            if (dfs(board, record, i + 1, j, cWord, currIndex)
                    || dfs(board, record, i - 1, j, cWord, currIndex)
                    || dfs(board, record, i, j + 1, cWord, currIndex)
                    || dfs(board, record, i, j - 1, cWord, currIndex)){
                return true;
            }else {
                record[i][j] = false;
                return false;
            }

        } else {
            record[i][j] = false;
            return false;
        }

    }


    public static void main(String[] args) {
        System.out.println(new WordSearch().exist(new char[][]{new char[]{'a', 'b'}, new char[]{'c', 'd'}}, "cdba"));
    }
//    public boolean exist(char[][] board, String word) {
//        Map<Character, Integer> map = new HashMap<>();
//        for(int i = 0; i<word.length() ; i++){
//            if(map.containsKey(word.charAt(i))){
//                map.put(word.charAt(i), map.get(word.charAt(i))+1);
//            }else{
//                map.put(word.charAt(i), 1);
//            }
//        }
//        // bfs
//        char[][] record = new char[board.length][board[0].length];
//        for(int i = 0; i < board.length; i++){
//            for(int j = 0; j < board[0].length; j++){
//                if(record[i][j]!=0){
//                    if(bfs(board, record, i, j, new HashMap<>(map))){
//                        return true;
//                    }
//                }
//            }
//        }
//        // dfs
//        char[][] record = new char[board.length][board[0].length];
//        for(int i = 0; i < board.length; i++){
//            for(int j = 0; j < board[0].length; j++){
//                if(record[i][j]!=0){
//                    if(dfs(board, record, i, j, new HashMap<>(map))){
//                        return true;
//                    }
//                }
//            }
//        }
//        return false;
//    }
//
//    boolean bfs(char[][] board, char[][] record, int i, int j, Map<Character, Integer> map){
//
//        if(map.size() == 0){
//            return true;
//        }
//        record[i][j] = 1;
//        char curr = board[i][j];
//        if(map.containsKey(curr)){
//            int count = map.get(curr);
//            count--;
//            if(count == 0){
//                map.remove(curr);
//            }else{
//                map.put(curr, count);
//            }
//            return bfs(board, record, i+1, j) || bfs(board, record, i-1, j) ||
//                    bfs(board, record, i, j+1) || bfs(board, record, i, j-1);
//
//        }else{
//            return false;
//        }
//
//    }
//
//    boolean dfs(char[][] board, char[][] record, int i, int j, Map<Character, Integer> map){
//
//        if(map.size() == 0){
//            return true;
//        }
//        char curr = board[i][j];
//        if(map.containsKey(curr)){
//
//        }else{
//            return false;
//        }
//
//    }
}
